"""
322. 零钱兑换
力扣题目链接

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：

输入：coins = [2], amount = 3
输出：-1
示例 3：

输入：coins = [1], amount = 0
输出：0
示例 4：

输入：coins = [1], amount = 1
输出：1
示例 5：

输入：coins = [1], amount = 2
输出：2
提示：

1 <= coins.length <= 12
1 <= coins[i] <= 2^31 - 1
0 <= amount <= 10^4
"""
from typing import List


class Solution:
    
    """
    定义dp数组，dp[i][j]表示凑成金额j时，可以使用硬币0~i的所需要的最少硬币数
    
    dp[i-1][j]表示凑成金额j时，可以使用硬币0~i-1的硬币所需要最少的硬币数
    
    递推公式：
    dp[i][j] = min(dp[i-1][j], dp[i][j-coins[i]] + 1)
    初始化：
    dp[i][0] = 0
    遍历方式：任意顺序，硬币和金额
    """
    # 二维dp
    def coinChange(self, coins: List[int], amount: int) -> int:
        # 1. 定义dp数组
        dp = [[0] * (amount+1) for i in coins]
        # 2. 初始化
        for j in range(amount+1):
            # 因为求最小个数所以用inf初始化
            dp[0][j] = float('inf') if j % coins[0] != 0 else j // coins[0]
        for i in range(len(coins)):
            dp[i][0] = 0
        # 3. 递推
        for i in range(1, len(coins)):
            for j in range(1, amount+1):
                if j >= coins[i]:
                    # print(i)
                    dp[i][j] = min(dp[i-1][j], dp[i][j-coins[i]] + 1)
                else:
                    dp[i][j] = dp[i-1][j]
        if dp[-1][-1] == float('inf'): return -1
        return dp[-1][-1]
    
    # 一维dp
    def coinChange(self, coins: List[int], amount: int) -> int:
        # 1. 定义dp数组
        dp = [float('inf')] * (amount+1)
        # 2. 初始化
        dp[0] = 0
        # 3. 递推
        for i in range(len(coins)):
            for j in range(1, amount+1):
                if j >= coins[i]:
                    dp[j] = min(dp[j], dp[j-coins[i]] + 1)
                else:
                    dp[j] = dp[j]
        if dp[-1] == float('inf'): return -1
        return dp[-1]
    
    # def coinChange(self, coins: List[int], amount: int) -> int:
    #     # 1. 定义dp数组
    #     dp = [[float('inf')] * (amount+1) for i in coins]
    #     # 2. 初始化
    #     for i in range(len(coins)):
    #         dp[i][0] = 0
    #     # 3. 递推
    #     for i in range(len(coins)):
    #         for j in range(1, amount+1):
    #             if i == 0:
    #                 dp[i][j] = float('inf') if j % coins[i] != 0 else j // coins[i]
    #                 continue
    #             if j >= coins[i]:
    #                 dp[i][j] = min(dp[i-1][j], dp[i][j-coins[i]] + 1)
    #             else:
    #                 dp[i][j] = dp[i-1][j]
    #     if dp[-1][-1] == float('inf'): return -1
    #     return dp[-1][-1]
    
    # def coinChange(self, coins: List[int], amount: int) -> int:
    #     # 1. 定义dp数组
    #     dp = [[-1] * (amount+1) for i in coins]
    #     # 2. 初始化
    #     for i in range(len(coins)):
    #         dp[i][0] = 0
    #     # 3. 递推
    #     for i in range(len(coins)):
    #         for j in range(1, amount+1):
    #             # 0号硬币单独处理
    #             if i == 0 and j % coins[i] == 0:
    #                 dp[i][j] = j // coins[i]
    #                 continue
    #             if j >= coins[i]:
    #                 # 用-1初始化，需要单独处理-1的情况，因为-1表示无效
    #                 if dp[i][j-coins[i]] == -1 and dp[i-1][j]==-1:
    #                     dp[i][j] = -1
    #                 elif  dp[i][j-coins[i]] == -1:
    #                     dp[i][j] = dp[i-1][j]
    #                 elif dp[i-1][j]==-1:
    #                     dp[i][j] = dp[i][j-coins[i]] + 1
    #                 else:
    #                     dp[i][j] = min(dp[i-1][j], dp[i][j-coins[i]] + 1)
    #             else:
    #                 dp[i][j] = dp[i-1][j]
    #     return dp[-1][-1]
        
        
        

if __name__ == "__main__":
    s = Solution()
    
    coins = [1, 2, 5]
    amount = 11
    
    # coins = [2]
    # amount = 3
    
    # coins = [2,5,10,1]
    # amount = 27
    

    n = s.coinChange(coins, amount)
    print(n)